home *** CD-ROM | disk | FTP | other *** search
/ Chip 1997 May / CHIP Mayıs 1997.iso / qtools / qbsp / csg4.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-12  |  8.5 KB  |  465 lines
  1. // csg4.c
  2.  
  3. #include "bsp5.h"
  4.  
  5. /*
  6.  
  7. NOTES
  8. -----
  9. Brushes that touch still need to be split at the cut point to make a tjunction
  10.  
  11. */
  12.  
  13. face_t    *validfaces[MAX_MAP_PLANES];
  14.  
  15.  
  16. face_t    *inside, *outside;
  17. int        brushfaces;
  18. int        csgfaces;
  19. int        csgmergefaces;
  20.  
  21. void DrawList (face_t *list)
  22. {
  23.     for ( ; list ; list=list->next)
  24.         Draw_DrawFace (list);
  25. }
  26.  
  27.  
  28. /*
  29. ==================
  30. NewFaceFromFace
  31.  
  32. Duplicates the non point information of a face, used by SplitFace and
  33. MergeFace.
  34. ==================
  35. */
  36. face_t *NewFaceFromFace (face_t *in)
  37. {
  38.     face_t    *newf;
  39.     
  40.     newf = AllocFace ();
  41.  
  42.     newf->planenum = in->planenum;
  43.     newf->texturenum = in->texturenum;    
  44.     newf->planeside = in->planeside;
  45.     newf->original = in->original;
  46.     newf->contents[0] = in->contents[0];
  47.     newf->contents[1] = in->contents[1];
  48.     
  49.     return newf;
  50. }
  51.  
  52.  
  53. /*
  54. ==================
  55. SplitFace
  56.  
  57. ==================
  58. */
  59. void SplitFace (face_t *in, plane_t *split, face_t **front, face_t **back)
  60. {
  61.     vec_t    dists[MAXEDGES+1];
  62.     int        sides[MAXEDGES+1];
  63.     int        counts[3];
  64.     vec_t    dot;
  65.     int        i, j;
  66.     face_t    *newf, *new2;
  67.     vec_t    *p1, *p2;
  68.     vec3_t    mid;
  69.     
  70.     if (in->numpoints < 0)
  71.         Error ("SplitFace: freed face");
  72.     counts[0] = counts[1] = counts[2] = 0;
  73.  
  74. // determine sides for each point
  75.     for (i=0 ; i<in->numpoints ; i++)
  76.     {
  77.         dot = DotProduct (in->pts[i], split->normal);
  78.         dot -= split->dist;
  79.         dists[i] = dot;
  80.         if (dot > ON_EPSILON)
  81.             sides[i] = SIDE_FRONT;
  82.         else if (dot < -ON_EPSILON)
  83.             sides[i] = SIDE_BACK;
  84.         else
  85.             sides[i] = SIDE_ON;
  86.         counts[sides[i]]++;
  87.     }
  88.     sides[i] = sides[0];
  89.     dists[i] = dists[0];
  90.     
  91.     if (!counts[0])
  92.     {
  93.         *front = NULL;
  94.         *back = in;
  95.         return;
  96.     }
  97.     if (!counts[1])
  98.     {
  99.         *front = in;
  100.         *back = NULL;
  101.         return;
  102.     }
  103.     
  104.     *back = newf = NewFaceFromFace (in);
  105.     *front = new2 = NewFaceFromFace (in);
  106.     
  107. // distribute the points and generate splits
  108.  
  109.     for (i=0 ; i<in->numpoints ; i++)
  110.     {
  111.         if (newf->numpoints > MAXEDGES || new2->numpoints > MAXEDGES)
  112.             Error ("SplitFace: numpoints > MAXEDGES");
  113.  
  114.         p1 = in->pts[i];
  115.         
  116.         if (sides[i] == SIDE_ON)
  117.         {
  118.             VectorCopy (p1, newf->pts[newf->numpoints]);
  119.             newf->numpoints++;
  120.             VectorCopy (p1, new2->pts[new2->numpoints]);
  121.             new2->numpoints++;
  122.             continue;
  123.         }
  124.     
  125.         if (sides[i] == SIDE_FRONT)
  126.         {
  127.             VectorCopy (p1, new2->pts[new2->numpoints]);
  128.             new2->numpoints++;
  129.         }
  130.         else
  131.         {
  132.             VectorCopy (p1, newf->pts[newf->numpoints]);
  133.             newf->numpoints++;
  134.         }
  135.         
  136.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  137.             continue;
  138.             
  139.     // generate a split point
  140.         p2 = in->pts[(i+1)%in->numpoints];
  141.         
  142.         dot = dists[i] / (dists[i]-dists[i+1]);
  143.         for (j=0 ; j<3 ; j++)
  144.         {    // avoid round off error when possible
  145.             if (split->normal[j] == 1)
  146.                 mid[j] = split->dist;
  147.             else if (split->normal[j] == -1)
  148.                 mid[j] = -split->dist;
  149.             else
  150.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  151.         }
  152.     
  153.         VectorCopy (mid, newf->pts[newf->numpoints]);
  154.         newf->numpoints++;
  155.         VectorCopy (mid, new2->pts[new2->numpoints]);
  156.         new2->numpoints++;
  157.     }
  158.  
  159.     if (newf->numpoints > MAXEDGES || new2->numpoints > MAXEDGES)
  160.         Error ("SplitFace: numpoints > MAXEDGES");
  161.  
  162. #if 0    
  163. CheckFace (newf);
  164. CheckFace (new2);
  165. #endif
  166.  
  167. // free the original face now that is is represented by the fragments
  168.     FreeFace (in);
  169. }
  170.  
  171. /*
  172. =================
  173. ClipInside
  174.  
  175. Clips all of the faces in the inside list, possibly moving them to the
  176. outside list or spliting it into a piece in each list.
  177.  
  178. Faces exactly on the plane will stay inside unless overdrawn by later brush
  179.  
  180. frontside is the side of the plane that holds the outside list
  181. =================
  182. */
  183. void ClipInside (int splitplane, int frontside, qboolean precedence)
  184. {
  185.     face_t    *f, *next;
  186.     face_t    *frags[2];
  187.     face_t    *insidelist;
  188.     plane_t *split;
  189.     
  190.     split = &planes[splitplane];
  191.     
  192.     insidelist = NULL;
  193.     for (f=inside ; f ; f=next)
  194.     {
  195.         next = f->next;
  196.         
  197.         if (f->planenum == splitplane)
  198.         {    // exactly on, handle special
  199.             if ( frontside != f->planeside || precedence )
  200.             {    // allways clip off opposite faceing
  201.                 frags[frontside] = NULL;
  202.                 frags[!frontside] = f;
  203.             }
  204.             else
  205.             {    // leave it on the outside
  206.                 frags[frontside] = f;
  207.                 frags[!frontside] = NULL;
  208.             }
  209.         }
  210.         else
  211.         {    // proper split
  212.             SplitFace (f, split, &frags[0], &frags[1]);
  213.         }
  214.         
  215.         if (frags[frontside])
  216.         {
  217.             frags[frontside]->next = outside;
  218.             outside = frags[frontside];
  219.         }
  220.         if (frags[!frontside])
  221.         {
  222.             frags[!frontside]->next = insidelist;
  223.             insidelist = frags[!frontside];
  224.         }
  225.     }
  226.     
  227.     inside = insidelist;
  228. }
  229.  
  230.  
  231. /*
  232. ==================
  233. SaveOutside
  234.  
  235. Saves all of the faces in the outside list to the bsp plane list
  236. ==================
  237. */
  238. void SaveOutside (qboolean mirror)
  239. {
  240.     face_t    *f , *next, *newf;
  241.     int        i;
  242.     int        planenum;
  243.         
  244.     for (f=outside ; f ; f=next)
  245.     {
  246.         next = f->next;
  247.         csgfaces++;
  248.         Draw_DrawFace (f);
  249.         planenum = f->planenum;
  250.         
  251.         if (mirror)
  252.         {
  253.             newf = NewFaceFromFace (f);
  254.             
  255.             newf->numpoints = f->numpoints;
  256.             newf->planeside = f->planeside ^ 1;    // reverse side
  257.             newf->contents[0] = f->contents[1];
  258.             newf->contents[1] = f->contents[0];
  259.     
  260.             for (i=0 ; i<f->numpoints ; i++)    // add points backwards
  261.             {
  262.                 VectorCopy (f->pts[f->numpoints-1-i], newf->pts[i]);
  263.             }
  264.         }
  265.         else
  266.             newf = NULL;
  267.  
  268.         validfaces[planenum] = MergeFaceToList(f, validfaces[planenum]);
  269.         if (newf)
  270.             validfaces[planenum] = MergeFaceToList(newf, validfaces[planenum]);
  271.  
  272.         validfaces[planenum] = FreeMergeListScraps (validfaces[planenum]);
  273.     }
  274. }
  275.  
  276. /*
  277. ==================
  278. FreeInside
  279.  
  280. Free all the faces that got clipped out
  281. ==================
  282. */
  283. void FreeInside (int contents)
  284. {
  285.     face_t    *f, *next;
  286.     
  287.     for (f=inside ; f ; f=next)
  288.     {
  289.         next = f->next;
  290.         
  291.         if (contents != CONTENTS_SOLID)
  292.         {
  293.             f->contents[0] = contents;
  294.             f->next = outside;
  295.             outside = f;
  296.         }
  297.         else
  298.             FreeFace (f);
  299.     }
  300. }
  301.  
  302.  
  303. //==========================================================================
  304.  
  305. /*
  306. ==================
  307. BuildSurfaces
  308.  
  309. Returns a chain of all the external surfaces with one or more visible
  310. faces.
  311. ==================
  312. */
  313. surface_t *BuildSurfaces (void)
  314. {
  315.     face_t            **f;
  316.     face_t            *count;
  317.     int                i;
  318.     surface_t        *s;
  319.     surface_t        *surfhead;
  320.     
  321.     surfhead = NULL;
  322.     
  323.     f = validfaces;
  324.     for (i=0 ; i<numbrushplanes ; i++, f++)
  325.     {
  326.         if (!*f)
  327.             continue;    // nothing left on this plane
  328.  
  329. // create a new surface to hold the faces on this plane
  330.         s = AllocSurface ();
  331.         s->planenum = i;
  332.         s->next = surfhead;
  333.         surfhead = s;
  334.         s->faces = *f;
  335.         for (count = s->faces ; count ; count=count->next)
  336.             csgmergefaces++;
  337.         CalcSurfaceInfo (s);    // bounding box and flags
  338.     }    
  339.     
  340.     return surfhead;
  341. }
  342.  
  343. //==========================================================================
  344.  
  345. /*
  346. ==================
  347. CopyFacesToOutside
  348. ==================
  349. */
  350. void CopyFacesToOutside (brush_t *b)
  351. {
  352.     face_t        *f, *newf;
  353.     
  354.     outside = NULL;
  355.     
  356.     for (f=b->faces ; f ; f=f->next)
  357.     {
  358.         brushfaces++;
  359. #if 0
  360. {
  361.     int        i;
  362.     
  363.     for (i=0 ; i<f->numpoints ; i++)
  364.         printf ("(%f,%f,%f) ",f->pts[i][0], f->pts[i][1], f->pts[i][2]);
  365.     printf ("\n");
  366. }
  367. #endif
  368.         newf = AllocFace ();
  369.         *newf = *f;
  370.         newf->next = outside;
  371.         newf->contents[0] = CONTENTS_EMPTY;
  372.         newf->contents[1] = b->contents;
  373.         outside = newf;
  374.     }
  375. }
  376.  
  377.  
  378. /*
  379. ==================
  380. CSGFaces
  381.  
  382. Returns a list of surfaces containing aall of the faces
  383. ==================
  384. */
  385. surface_t *CSGFaces (brushset_t *bs)
  386. {
  387.     brush_t        *b1, *b2;
  388.     int            i;
  389.     qboolean        overwrite;
  390.     face_t        *f;
  391.     surface_t    *surfhead;
  392.  
  393.     qprintf ("---- CSGFaces ----\n");
  394.  
  395.     memset (validfaces, 0, sizeof(validfaces));
  396.     
  397.     csgfaces = brushfaces = csgmergefaces = 0;
  398.     
  399.     Draw_ClearWindow ();
  400.     
  401. //
  402. // do the solid faces
  403. //
  404.     for (b1=bs->brushes ; b1 ; b1 = b1->next)
  405.     {
  406.     // set outside to a copy of the brush's faces
  407.         CopyFacesToOutside (b1);
  408.         
  409.         overwrite = false;
  410.         
  411.         for (b2=bs->brushes ; b2 ; b2 = b2->next)
  412.         {
  413.         // see if b2 needs to clip a chunk out of b1
  414.         
  415.             if (b1==b2)
  416.             {
  417.                 overwrite = true;    // later brushes now overwrite
  418.                 continue;
  419.             }
  420.  
  421.         // check bounding box first
  422.             for (i=0 ; i<3 ; i++)
  423.                 if (b1->mins[i] > b2->maxs[i] || b1->maxs[i] < b2->mins[i])
  424.                     break;
  425.             if (i<3)
  426.                 continue;
  427.  
  428.         // divide faces by the planes of the new brush
  429.         
  430.             inside = outside;
  431.             outside = NULL;
  432.             
  433.             for (f=b2->faces ; f ; f=f->next)
  434.                 ClipInside (f->planenum, f->planeside, overwrite);
  435.  
  436.         // these faces are continued in another brush, so get rid of them
  437.             if (b1->contents == CONTENTS_SOLID && b2->contents <= CONTENTS_WATER)
  438.                 FreeInside (b2->contents);
  439.             else
  440.                 FreeInside (CONTENTS_SOLID);
  441.         }
  442.         
  443.     // all of the faces left in outside are real surface faces
  444.         if (b1->contents != CONTENTS_SOLID)
  445.             SaveOutside (true);    // mirror faces for inside view
  446.         else
  447.             SaveOutside (false);
  448.     }
  449.  
  450. #if 0
  451.     if (!csgfaces)
  452.         Error ("No faces");
  453. #endif
  454.  
  455.     surfhead = BuildSurfaces ();
  456.     
  457.     qprintf ("%5i brushfaces\n", brushfaces);
  458.     qprintf ("%5i csgfaces\n", csgfaces);
  459.     qprintf ("%5i mergedfaces\n", csgmergefaces);
  460.     
  461.     return surfhead;
  462. }
  463.  
  464.  
  465.